package com.jn.algorithm.day026.question84;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 江南大学1033190417
 * @date 2022/5/17 12:59
 */
public class Solution {
    //暴力解法//超时
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int max = 0, l, r;
        for (int i = 0; i < n; i++) {
            int curHeight = heights[i];
            l = i;
            r = i;
            while (l >= 0 && heights[l] >= curHeight) {
                --l;
            }
            while (r < n && heights[r] >= curHeight) {
                ++r;
            }
            int area = (r - l - 1) * curHeight;
            max = Math.max(max, area);
        }
        return max;
    }

    //栈
    public int largestRectangleArea2(int[] heights) {
        int area = 0;
        int len = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.pollLast()];
                while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.pollLast();
                }
                int width;
                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peekLast() - 1;
                }
                area = Math.max(area, width * height);
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pollLast()];
            while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                stack.pollLast();
            }
            int width;
            if (stack.isEmpty()) {
                width = len;
            } else {
                width = len - stack.peekLast() - 1;
            }
            area = Math.max(area, width * height);
        }
        return area;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{2, 1, 5, 6, 2, 3};
        System.out.println(solution.largestRectangleArea2(nums));
    }
}
